package com.example.learn.red_black_tree;

import java.util.ArrayList;
import java.util.List;

public class AbstractTree {

    //nil节点 红黑树
    protected static final Node nilNode = new Node(RedBlackTree.class, null, null, null, null, Node.Color.BLACK);
    public List<Integer> elementList = new ArrayList<Integer>();
    public Node root;

    //左旋操作 红黑树 以某个节点为旋转点,该节点的右子节点变为该节点的父节点,该节点变为右子节点的左子节点,该节点的右子节点的左子节点变为该节点的右节点
    protected Node rotateLeft(Node node) {
        Node temp = node.right;
        temp.parent = node.parent;
        node.right = temp.left;
        if (isNotNilOrNullNode(node.right)) {
            node.right.parent = node;
        }
        temp.left = node;
        node.parent = temp;

        if (isNotNilOrNullNode(temp.parent)) {
            root = temp;
        } else {
            if (temp.parent.left == node) {
                temp.parent.left = temp;
            } else {
                temp.parent.right = temp;
            }
        }

        return temp;

    }

    //右旋 红黑树 以某个节点为旋转点,该节点的左子节点变为该节点的父节点，该节点变为左子节点的右子节点,该节点的左子节点的右节点变为该节点的左节点
    protected Node rotateRight(Node node) {
        Node temp = node.left;
        temp.parent = node.parent;
        node.left = temp.right;
        temp.right = node;
        node.parent = temp;
        if (isNotNilOrNullNode(node.left)) {
            node.left.parent = node;
        }
        if (isNotNilOrNullNode(temp.parent)) {
            root = temp;
        } else {
            if (temp.parent.left == node) {
                temp.parent.left = temp;
            } else {
                temp.parent.right = temp;
            }
        }

        return temp;

    }


    public boolean isNotNilOrNullNode(Node node) {
        return !(node == null || node == nilNode);
    }

    protected String printSubTree(Node node) {
        StringBuffer tree = new StringBuffer();
        if (node.right != null) {
            printTree(node.right, true, "", tree);
        }
        printNodeValue(node, tree);
        if (node.left != null) {
            printTree(node.left, false, "", tree);
        }
        return tree.toString();


    }

    private void printTree(Node node, boolean isRight, String indent, StringBuffer tree) {
        if (node.right != null) {
            printTree(node.right, true, indent + (isRight ? "         " : " |       "), tree);
        }
        tree.append(indent);
        if (isRight) {
            tree.append(" /");
        } else {
            tree.append(" \\");
        }
        tree.append("------ ");
        printNodeValue(node, tree);
        if (node.left != null) {
            printTree(node.left, false, indent + (isRight ? " |       " : "         "), tree);
        }
    }

    private void printNodeValue(Node node, StringBuffer tree) {
        if (node.value == null) {
            tree.append("<NIL>");
        } else {
            tree.append(node.value);
            if (root.clazz.equals(RedBlackTree.class)) {
                tree.append("(").append(node.color == Node.Color.BLACK ? "黑" : "红").append(")");
            }
        }
        tree.append("\r\n");
    }

}
